/*
 * 版权所有(C)，方太互联网应用技术部，lizhixing，所有权利保留。
 * <p>
 * 项目名：	algorithm-demo
 * 文件名：	FifthQuantity
 * 模块说明：
 * 修改历史：
 * 2025/1/13 - lizhixing - 创建。
 */
package com.lovely602.algorithm.wansuanfa;

/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
 * <p>
 * <p>
 * 示例1： 输入：s = "babad"
 * <p>
 * 输出："bab"
 * <p>
 * 解释："aba" 同样是符合题意的答案。
 * <p>
 * 示例2： 输入：s = "cbbd"
 * <p>
 * 输出："bb"
 * <p>
 * <p>
 * 1 <= s.length <= 1000
 * <p>
 * s 仅由数字和英文字母组成
 *
 * @author lizhixing
 */
public class Question005 {

    public static void main(String[] args) {

        String str = "cbbd";
//    String str = "babad";

        Question005 question = new Question005();

        String palindrome = question.longestPalindrome(str);

        System.out.println(palindrome);
    }

    public String longestPalindrome(String s) {
        // start表示最长回文子串开始的位置，为了后面截取。
        // maxLen表示最长回文子串的长度
        int start = 0, maxLen = 1;
        int length = s.length();
        boolean[][] dp = new boolean[length][length];
        for (int right = 1; right < length; right++) {
            for (int left = 0; left < right; left++) {
                // 如果两种字符不相同，肯定不能构成回文子串。
                if (s.charAt(left) != s.charAt(right))
                    continue;
                // 下面是s[left]和s[right]两个字符相同情况下的判断。
                if (right - left <= 2) {
                    // 类似于"a"，"aa"和"aba"，也是回文子串。
                    dp[left][right] = true;
                } else {
                    // 类似于"a******a"，要判断他是否是回文子串，只需要
                    // 判断"******"是否是回文子串即可。
                    dp[left][right] = dp[left + 1][right - 1];
                }
                // 如果字符串从left到right是回文子串，保存最长的回文子串。
                if (dp[left][right] && right - left + 1 > maxLen) {
                    maxLen = right - left + 1;
                    start = left;
                }
            }
        }
        // 截取最长的回文子串
        return s.substring(start, start + maxLen);
    }

}
